package com.zk.algorithm.greedy;

import com.zk.algorithm.annotation.TiaoZhanChengXuSheJiJingSai;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 优先队列问题
 *
 * 驾驶一辆卡车行驶 L 单位距离。最开始有 P 升汽油，N 个加油站，i 在距离起点 Ai 单位距离的地方，最多加油 Bi 升，
 * 求最少加油次数
 *
 * @author zk
 */
@TiaoZhanChengXuSheJiJingSai
public class Expedition {

    /**
     * 最少加油次数
     *
     * @param A 距离
     * @param B 加多少油
     * @param L 总距离
     * @param P 一开始的汽油数
     * @return
     */
    public int minGasNumber(int[] A, int[] B, int L, int P) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -o1.compareTo(o2);
            }
        });

        // 加油次数
        int ans = 0;
        // 加油站个数
        int N = B.length;
        // 现在位置
        int pos = 0;
        // 油箱中的量
        int tank = P;

        for (int i = 0; i < N; i++) {
            // 接下来要走多远
            int d = A[i] - pos;
            // 不断加油直到足够行驶到下一加油站
            //
            // 一升油走一单位距离
            while (tank - d < 0) {
                if (queue.isEmpty()) {
                    return -1;
                }

                tank += queue.poll();
                ans++;
            }

            // 我们走完了
            tank -= d;
            // 我们到 A[i] 了
            pos = A[i];
            // 我们放进去下一个加油站的油
            queue.offer(B[i]);
        }

        return ans;
    }

}